// 使用动态规划实现最小编辑距离
// ref: 力扣72题 零钱兑换 https://leetcode.cn/problems/edit-distance/description


#include <vector>
#include <string>
#include <iostream>
#include <limits.h>


/**
 *! @brief 使用动态规划实现word1编程word2的最少编辑次数，俗称编辑距离 
 * 
 * @param word1   源单词
 * @param word2   目标单词
 * 
 * @return int    最少的编辑次数
 */
int mindpistance(std::string word1, std::string word2) {
    int n = word1.length();
    int m = word2.length();

    // 有一个字符串为空串
    if (n * m == 0) return n + m;

    // dp 数组
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1));

    // 边界状态初始化
    for (int i = 0; i < n + 1; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j < m + 1; j++) {
        dp[0][j] = j;
    }

    // 计算所有 dp 值
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < m + 1; j++) {
            int left = dp[i - 1][j] + 1;
            int down = dp[i][j - 1] + 1;
            int left_down = dp[i - 1][j - 1];
            if (word1[i - 1] != word2[j - 1]) left_down += 1;
            dp[i][j] = std::min(left, std::min(down, left_down));

        }
    }
    return dp[n][m];
}


int main(int argc, char const *argv[]) {
    std::string word1 = "horse", word2 = "ros";

    int res = mindpistance(word1, word2);
    std::cout << res << std::endl;

    return 0;
}